import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class L39 {
    public static void main(String[] args) {
        int[] candidates = {2, 3, 6, 7};
        int target = 7;


        List<List<Integer>> lists = new Solution().combinationSum(candidates, target);
        for (List<Integer> integers : lists) {
            System.out.println(integers.toString());
        }
    }

//    static class Solution {
//        public List<List<Integer>> combinationSum(int[] candidates, int target) {
//            List<List<Integer>> res = new ArrayList<>();
//            Arrays.sort(candidates); // 先进行排序
//            backtracking(res, new ArrayList<>(), candidates, target, 0, 0);
//            return res;
//        }
//
//        public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
//            // 找到了数字和为 target 的组合
//            if (sum == target) {
//                res.add(new ArrayList<>(path));
//                return;
//            }
//
//            for (int i = idx; i < candidates.length; i++) {
//                // 如果 sum + candidates[i] > target 就终止遍历
//                if (sum + candidates[i] > target) {
//                    break;
//                }
//                path.add(candidates[i]);
//                backtracking(res, path, candidates, target, sum + candidates[i], i);
//                path.remove(path.size() - 1); // 回溯，移除路径 path 最后一个元素
//            }
//        }
//    }

    static class Solution {
        List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> tmp = new LinkedList<>();

        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            backTracking(candidates, target, 0);
            return result;
        }

        private void backTracking(int[] candidates, int target, int index) {
            if (target == 0) {
                result.add(new ArrayList<>(tmp));
                return;
            } else if (target < 0) {
                return;
            }

            for (int i = index; i < candidates.length; i++) {
                tmp.add(candidates[i]);
                target -= candidates[i];
                backTracking(candidates, target, i);
                target += tmp.getLast();
                tmp.removeLast();
            }

        }
    }
}
